A. Field of the Invention
This invention relates to a system for correcting erroneous data in the memories or data transmission of a data processing system. More particularly, it relates to such an error correcting system which minimizes the time delay for cyclic code processing using a minimum of special hardware.
B. Description of the Prior Art
As memory densities continue to increase so does the risk of errors. Alpha particles and electric noise plague the newer, denser semiconductor memories and surface damage on magnetic disks is becoming more troublesome now that bits are being crammed into smaller areas.
To remedy these problems, more and more manufacturers are adopting error-detection and correction schemes. The grandfather of them all uses the parity bit, which simply records whether the number of binary 1's in one memory location is even or odd and thus detects only single-bit errors. Luckily mathematicians are forever contriving new ways for the engineer to uncover even multiple bit errors.
Hamming codes have proved particularly useful in the semiconductor memory context. They append a fixed number of check bits to each byte or word of data. Upon reading from that location, the check bits will detect and correct all single-bit errors and will flag as impossible to correct all multibit errors.
One of the more advanced systems uses Fire code to protect and correct up to 12 erroneous bits. In this method, the repeated division of a data stream produces a fixed number of check bits that are appended to each disk record. When that same record is read, its check bits are used to detect, locate and correct any error bursts that might be due to imperfections in the disk surface.
The burst-error processor (BEP) is a hardware implementation of these codes. It operates by dividing the data stream, a byte at a time, by a fixed binary number represented mathematically by a polynominal; for example X.degree.+X.sup.2 +X.sup.5 +X.sup.7 stands for a binary 10100101 since each exponent indicates the position of a 1.
Even though the data stream is being constantly divided as it passes through the burst-error processor, the actual data remains unaffected. However at the end of the data transmission the internal registers of the processor contain the remainder of the division. For write operations, the remainder bits are appended to the data to produce a disk record. For read operations, the processor continues to divide the check bits after the data has passed to obtain a bit pattern called the syndrome. For error free operation, the syndrome should be 0. If it is not 0, it contains the information about the location of the error burst as well as the position of the errors.
In the error correction mode, the processor uses the syndrome to find first the error location and then the error pattern whichis exclusive-OR'd with the error burst to correct it.
Finally, past system implementations almost invariably involved the conventional shift register approach. That is, residue generation of a bit string was accomplished on a bit by bit basis in successive clock cycles.
The foregoing illustrates limitations of the known prior art. Thus, it is apparent that it would be advantageous to provide an alternative directed to overcoming one or more of the limitations as set forth above. Accordingly, a suitable alternative is to provide a high speed code processing for error correcting code.